# -*- coding: utf-8 -*-
# @Time : 2023/8/22 23:03
# @Author  : lining
# @FileName: 冗余连接.py
"""
https://leetcode.cn/problems/redundant-connection/
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
优化：O(n)时间复杂度进行遍历，先走一遍边，进行一次dfs
方法1：每个遍历过的点标记为true，当两个点都访问过就是有环，
用例[[1,2],[4,3],[3,2]] 3，2连个点都遍历过，但并没有形成环
解决方法：未遍历过的点标记为0，已经遍历过的点标记为1，如果遍历一圈，回到了1号标记的点则有环
当遍历到最后一个节点，已经没有后续节点了，就把这个路径上的节点都标记为2
取一个没遍历过的点走，当走到2号点，不是环
"""


class FindCycle():
    def __init__(self):
        # 已经遍历过的节点
        self.visited = {}
        # 图的节点数
        self.n = 0
        # 有环标记
        self.has_cycle = False
        self.cycle = []

    # 获取这个图有几个节点
    def getnode(self, edges):
        for i in edges:
            self.n = max(self.n, max(i))

    # 获取每个节点能去的边
    def get_to_edg(self, edges):
        self.to_edg = {}
        for i in edges:
            if i[0] not in self.to_edg:
                self.to_edg[i[0]] = [i[1]]
            else:
                self.to_edg[i[0]].append(i[1])
            # 边是双向的
            if i[1] not in self.to_edg:
                self.to_edg[i[1]] = [i[0]]
            else:
                self.to_edg[i[1]].append(i[0])

    # 深度优先遍历--找环
    def dfs(self, current, father):
        """
        :param current: 当前走的点
        :param father: 当前点的父节点，0代表没有
        :return:
        """
        # 这个点已经遍历过，如果已经遍历过就不再遍历
        self.visited[current] = True
        # 在to边数组遍历，找到环
        for i in self.to_edg[current]:
            # 类似，1-2，2-1这种不算环，要跳过
            if i == father:
                continue
            # 这个节点还没遍历过，就递归
            if i not in self.visited:
                self.dfs(i, current)
            # 有环
            else:
                self.has_cycle = True
                if self.cycle == []:
                    self.cycle = [i, current]
                    print(self.cycle)
                    return

# edges = [[1,2], [1,3], [2,3]]    # 结果不对
# edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
edges = [[2,7],[7,8],[3,6],[2,5],[6,8],[4,8],[2,8],[1,8],[7,10],[3,9]]
a = FindCycle()
a.get_to_edg(edges)
a.dfs(1,0)
